import com.sun.xml.internal.bind.v2.model.core.EnumLeafInfo;
import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author ZhengDp
 * @Date 2023/4/13 20:37
 */
public class 贪心算法 {

    /*
    * #problem 455 分发饼干
    * */
    // 1. 贪心算法
    // 对饼干和胃口进行排序，给胃口较小的人先分
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i =0,j=0;
        int res = 0;
        // g 胃口  s 饼干
        while(i<g.length  && j < s.length) {
            if(s[j] >= g[i]) {
                res ++;
                j++;
                i++;
            } else if(s[j] < g[i]) {
                j++;
            }
        }
        return res;
    }
    /*
    * #problem 322 零钱兑换
    * */
    // 1. 动态规划
    public int coinChange(int[] coins, int amount) {
        int size = coins.length;
        int[] dp = new int[amount+1];
        for(int i =1;i<=amount;i++) {
            dp[i] = -1;
            for(int j = 0;j< size;j++) {
                long preAmount = i - coins[j];
                if(preAmount >= 0 && dp[(int) preAmount] != -1) {
                    if(dp[i] == -1) {
                        dp[i] = dp[(int) preAmount] + 1;
                    } else {
                        dp[i] = Math.min(dp[i],dp[(int) preAmount] + 1);
                    }
                }
            }
        }
        return dp[amount];
    }

    // 2. 深搜 + 用数据记录计算过的值
    public int coinChange1(int[] coins, int amount) {
        if(amount < 1) {
            return 0;
        }
        return coinF(coins,amount,new int[amount+1]);
    }

    private int coinF(int[] coins,int amount , int[] count) {
        if(amount < 0) {
            return -1;
        }
        if(amount == 0) {
            return 0;
        }
        if(count[amount] != 0) {
            return count[amount];
        }
        int min = Integer.MAX_VALUE;
        for(int i =0;i<coins.length;i++) {
            int res = coinF(coins,amount-coins[i],count);
            if(res >=0 && res < min){
                min = Math.min(res+1,min);
            }
        }
        count[amount] = min == Integer.MAX_VALUE ? -1 : min;
        return count[amount];
    }

    /*
    * #problem 860 柠檬水找零
    * */
    // 先用大钱找零 --> 5 和 15 / 20 是倍数关系
    public boolean lemonadeChange(int[] bills) {
        Map<Integer,Integer> countMap = new HashMap<>();
        if(bills[0] != 5) {
            return false;
        }
        countMap.put(bills[0],1);
        boolean res = true;
        for(int i =1;i<bills.length && res;i++) {
            int bill = bills[i];
            int remain = bill-5;
            int tenNum = remain/10;
            int fiveNum = (remain%10)/5;
            if(countMap.getOrDefault(10,0) >= tenNum && countMap.getOrDefault(5,0) >= fiveNum) {
                countMap.put(10,countMap.getOrDefault(10,0)-tenNum);
                countMap.put(5,countMap.getOrDefault(5,0)-fiveNum);
            } else if(countMap.getOrDefault(5,0) >= remain/5){
                fiveNum = remain/5;
                countMap.put(5,countMap.getOrDefault(5,0)-fiveNum);
            } else {
                res = false;
            }
            countMap.put(bill,countMap.getOrDefault(bill,0) +1);
        }
        return res;
    }

    /*
    * #problem 122 买卖股票的最佳时机II
    * */
    // 1. 动态规划
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for(int i =1;i<prices.length;i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] - prices[i]);
        }
        return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);
    }

    // 2. 动态规划-空间优化

    public int maxProfit1(int[] prices) {
        int d0 = 0,d1 = -prices[0];
        for(int i=1;i<prices.length;i++) {
            int temp0 = d0;
            d0 = Math.max(d0,d1 + prices[i]);
            d1 = Math.max(d1,temp0 - prices[i]);
        }
        return Math.max(d0,d1);
    }


    /*
    * #problem 874 模拟行走机器人
    * */
    // 1. 模拟 +太慢了
    @Test
    void test(){
        robotSim(new int[]{7,-2,-2,7,5},new int[][] {{-3,2},{-2,1},{0,1},{-2,4},{-1,0},{-2,-3},{0,-3},{4,4},{-3,3},{2,2}});
    }
    Map<String,String> directMap = new HashMap<>();
    {
        directMap.put("N-1","E");
        directMap.put("N-2","W");
        directMap.put("E-1","S");
        directMap.put("E-2","N");
        directMap.put("S-1","W");
        directMap.put("S-2","E");
        directMap.put("W-1","N");
        directMap.put("W-2","S");
    }
    public int robotSim(int[] commands, int[][] obstacles) {
        int x = 0,y=0;
        int res = 0;
        String forward = "N";

        for(int i = 0;i<commands.length;i++) {
            // 模拟操作
            int command = commands[i];
            if(command < 0) {
                // 转向
                forward = directMap.get(forward + command);
            } else {
                // 前进
                int tx = x;
                int ty = y;
                switch (forward) {
                    case "N":
                        ty += command;
                        break;
                    case "E":
                        tx += command;
                        break;
                    case "S":
                        ty -= command;
                        break;
                    case "W":
                        tx -= command;
                        break;
                }
                int[] temp = judgeObstacle(tx,ty,command,forward,obstacles);
                if(temp == null) {
                    x = tx;
                    y = ty;
                } else {
                    x = temp[0];
                    y = temp[1];
                }
                res = (int) Math.max(res,Math.pow(x,2)+Math.pow(y,2));
            }
        }
        return res;
    }

    private int[] judgeObstacle(int x,int y ,int command, String forward,int[][] obstacles) {
        List<int[]> t1 = new ArrayList<>();
        Comparator<int[]> comparator = null;
        for(int i = 0;i<obstacles.length;i++) {
            int[] temp = obstacles[i];
            int tx = temp[0];
            int ty = temp[1];
            switch (forward) {
                case "N":
                    if(tx == x) {
                        t1.add(temp);
                    }
                    comparator = new Comparator<int[]>() {
                        @Override
                        public int compare(int[] o1, int[] o2) {
                            return o1[1] - o2[1];
                        }
                    };
                    break;
                case "S":
                    if(tx == x) {
                        t1.add(temp);
                    }
                    // 降序
                    comparator = new Comparator<int[]>() {
                        @Override
                        public int compare(int[] o1, int[] o2) {
                            return o2[1] - o1[1];
                        }
                    };
                    break;
                case "E":
                    if(ty == y) {
                        t1.add(temp);
                    }
                    comparator = new Comparator<int[]>() {
                        @Override
                        public int compare(int[] o1, int[] o2) {
                            return o1[0] - o2[0];
                        }
                    };
                    break;
                case "W":
                    if(ty == y) {
                        t1.add(temp);
                    }
                    comparator = new Comparator<int[]>() {
                        @Override
                        public int compare(int[] o1, int[] o2) {
                            return o2[0] - o1[0];
                        }
                    };
                    break;
            }
        }
        t1.sort(comparator);
        for(int[] temp : t1) {
            int tx = temp[0];
            int ty = temp[1];
            switch (forward) {
                case "N":
                    if(tx == x && y - command < ty && y >= ty) {
                        return new int[]{x,ty-1};
                    }
                    break;
                case "E":
                    if(ty == y && x- command < tx &&  x  >= tx) {
                        return new int[]{tx-1,y};
                    }
                    break;
                case "S":
                    if(tx == x && y + command > ty &&  y  <= ty) {
                        return new int[]{x,ty+1};
                    }
                    break;
                case "W":
                    if(ty == y && x + command> tx && x  <= tx) {
                        return new int[]{tx+1,y};
                    }
                    break;
            }
        }
        return null;
    }

    // 2. 写法优化
    public int robotSim1(int[] commands, int[][] obstacles) {
        int[] dx = {0,1,0,-1};
        int[] dy = {1,0,-1,0};
        int x = 0,y=0,di=0;
        int res = 0;
        Set<String> dict = new HashSet<>();
        for(int i =0;i<obstacles.length;i++) {
            int[] t = obstacles[i];
            int row = t[0];
            int col = t[1];
            dict.add(row + "_" + col);
        }
        for(int i = 0;i<commands.length;i++) {
            int command = commands[i];
            if(command == -1) {// 右转
                di = (di + 3) %4;
            } else if(command == -2) { // 左转
                di = (di+1)%4;
            } else {
                for(int k = 0;k<command;k++) {
                    int tx = x + dx[di];
                    int ty = y + dy[di];
                    String key = tx + "_" + ty;
                    if(dict.contains(key)) {
                        break;
                    } else {
                        x = tx;
                        y = ty;
                        res = Math.max(res,x*x+y*y);
                    }
                }
            }
        }
        return res;
    }

    /*
    * #problem 55.跳跃游戏
    * */
    @Test
    void testCanJump(){
        canJump1(new int[]{1,2});
    }
    // 1. 动态规划
    public boolean canJump(int[] nums) {
        boolean[] dp = new boolean[nums.length];
        dp[0] = true;
        for(int i =0;i<nums.length-1 & !dp[nums.length];i++) {
            int len = nums[i];
            if(!dp[i]) {
                continue;
            }
            for(int k = 1;k<=len && i+k < nums.length;k++) {
                 dp[i+k] = dp[i+k] || dp[i];
            }
        }
        return dp[nums.length-1];
    }

    // 2. 贪心 --> 维护一个最大右边界 ==> 因为如果 nums[i]可以跳到 nums[i+n],那么它一定可以跳到nums[i+1 ~ i+n]
    public boolean canJump1(int[] nums) {
        int rightM = 0;
        for(int i =0;i<nums.length;i++) {
            // 当前位置可达
            if(i <= rightM) {
                rightM = Math.max(rightM,nums[i] + i);
            }
            if(rightM >= nums.length-1) {
                return true;
            }
        }
        return false;
    }

    /*
    * #problem 45 跳跃游戏II
    * */
    @Test
    void jumpTest(){
        jump(new int[]{1,2});
    }
    // 1. 动态规划
    public int jump(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i =0;i<nums.length-1;i++) {
            // 当前位置不可达
            if(dp[i] == Integer.MAX_VALUE) {
                continue;
            }
            int len = nums[i];
            for(int step = 1;step<=len && i+step < nums.length;step++) {
                dp[i+step] = Math.min(dp[i+step],dp[i] + 1);
            }
        }
        return dp[nums.length-1];
    }

    // 2. 贪心算法
    // 记录每一步能够到达的最大右边界，然后找到在这个边界能够到达的最大右边界
    public int jump2(int[] nums) {
        int step = 0;
        // 每一步可以到达的最大右边界
        int maxRight = 0;
        // 当前步的边界（上一次的最大右边界）
        int end = 0;
        for(int i =0;i<nums.length;i++) {
            maxRight = Math.max(maxRight,i + nums[i]);
            if(i == end ) {
                // 到达当前的右边界，需要进行下一步了
                end = maxRight;
                step++;
            }
        }
        return step;

    }
}
